package Code;

import java.util.HashMap;
import java.util.Map;

public class Code146 {
    static class DLinkedNode{
        int key;
        int val;
        DLinkedNode prev;
        DLinkedNode next;
        DLinkedNode(){}
        DLinkedNode(int k, int v){
            key = k;
            val = v;
        }
    }
    Map<Integer, DLinkedNode> map = new HashMap<>();
    int size = 0;
    int capacity = 0;
    DLinkedNode head, tail;
    Code146(int capacity){
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    int get(int key){
        DLinkedNode node = map.get(key);
        if(node == null) return -1;
        moveToHead(node);
        return node.val;
    }
    void put(int key, int val){
        DLinkedNode node = map.get(key);
        if(node == null) {
            DLinkedNode newNode = new DLinkedNode(key, val);
            map.put(key, newNode);
            addToHead(newNode);
            size++;
            if(size > capacity){
                DLinkedNode removed = removeTail();
                map.remove(removed.key);
                size--;

            }
        }else{
            node.val = val;
            moveToHead(node);
        }


    }

    DLinkedNode removeTail(){
        DLinkedNode removed = tail.prev;
        removeNode(removed);
        return removed;
    }
    void removeNode(DLinkedNode node){
        node.next.prev = node.prev;
        node.prev.next= node.next;

    }
    void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);

    }
    public static void main(String[] args) {
        Code146 c = new Code146(2);
        c.put(1, 1);
        c.put(2, 2);
        System.out.println(c.get(1));
    }
}
